این مقاله ترجمه مقاله انگلیسی Communication Optimal Parallel Multiplication
of Sparse Random Matrices می باشد ./

سال انتشار : 2013 /

تعداد صفحه مقاله انگلیسی : 10 / pdf

تعداد صفحه فایل ترجمه : 20/

فرمت فایل ترجمه : Word /

چکیده

الگوریتم های موازی برای ضرب ماتریس های اسپارس به طور معمول به جای صرف بیشتر وقت خود برای محاسبات، آن را صرف ارتباطات میان پردازشگر می کنند، و پیش بینی می شود که از نظر گرایش های سخت افزاری هزینه نسبی ارتباطات تنها افزایش خواهد یافت. بنابراین، الگوریتم های ضرب ماتریس اسپارس باید هزینه های ارتباطی را به حداقل برسانند تا هم تراز شمارش [کلاک]  پردازنده بزرگ باشند.

در این مقاله، ضرب ماتریس های اسپارس مربوط به نمودار های تصادفی Erdos-Renyi بر روی ماشین های موازی با حافظه توزیع شده در نظر گرفته شده است. برای کلاس گسترده ای از الگوریتم ها در هزینه های ارتباطی مورد انتظار کران پایینی به دست آمده است. تجزیه و تحلیل الگوریتم های موجود نشان می دهد، در حالی که برخی از آنها برای طیف محدودی چگالی ماتریس و تعداد پردازنده ها مطلوب اند، هیچ کدام به طور کلی مطلوب نیستند. دو الگوریتم موازی به دست آمده و ثابت می شود که آنها با کران پایین هزینه های ارتباطی مورد انتظار مطابقت دارند، و از این رو آنها مطلوب هستند./1009/